Théorème d'Euler, chaîne eulérienne et cycle eulérien

Définitions Chaîne eulérienne, cycle eulérien

• Une chaîne est eulérienne si elle contient une fois et une seule chaque arête du graphe.
  
• Si la chaîne est un cycle, on dit que c’est un cycle eulérien.
  

Théorème d’Euler

Un graphe connexe a une chaîne eulérienne si et seulement si tous ses sommets ont un degré pair, sauf au plus deux.

Remarques

On a vu précédemment que le nombre de sommets avec un degré impair est forcément pair, donc on peut reformuler de la façon suivante.

• Si un graphe connexe n’a pas de sommet de degré impair, alors il existe une chaîne eulérienne, qui de plus est un cycle.
  
• Si un graphe connexe a exactement deux sommets de degré impair, alors il existe une chaîne eulérienne dont ces deux sommets sont nécessairement les extrémités. Cette chaîne ne peut donc pas être un cycle.
• Dans tous les autres cas, il n’existe pas de chaîne eulérienne.
  

Remarquons aussi qu'en général il n'y a pas unicité de la chaîne eulérienne trouvée (voir exemples).

Théorème Cycle orienté eulérien dans un graphe orienté

Un graphe orienté connexe possède un cycle orienté eulérien si et seulement si de chaque sommet il part autant d’arêtes qu’il en arrive.